package leecode

import "sort"

func permutation2(S string) (result []string) {
	arr := []byte(S)
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})
	used := make([]bool, len(arr))
	path := make([]byte, 0, len(arr))
	var backtracking func()
	backtracking = func() {
		if len(path) == len(arr) {
			temp := make([]byte, len(arr))
			copy(temp, path)
			result = append(result, string(temp))
			return
		}
		for i := 0; i < len(arr); i++ {
			if used[i] || (i > 0 && arr[i-1] == arr[i] && used[i-1] == false) {
				continue
			}
			used[i] = true
			path = append(path, arr[i])
			backtracking()
			used[i] = false
			path = path[:len(path)-1]
		}
	}
	backtracking()
	return
}
